package server.game.world.map;

import java.util.ArrayList;
import java.util.LinkedList;

import server.game.Constants;
import server.game.entity.character.utils.Path;

//A very typical A* pathfinding methodology

public class PathFinding {

	private Region region;
	private Node[][] nodes;

	public PathFinding(Region region) {
		this.region = region;
		generateNodeArray();
	}

	public void generateNodeArray() {
		nodes = new Node[Constants.REGION_SIZE][Constants.REGION_SIZE];
		for (int x = 0; x < Constants.REGION_SIZE; x++) {
			for (int y = 0; y < Constants.REGION_SIZE; y++) {
				nodes[x][y] = new Node(region.getTile(x, y));
			}
		}
	}

	public Path findPath(Tile startTile, Tile endTile) {
		for (int x = 0; x < Constants.REGION_SIZE; x++) {
			for (int y = 0; y < Constants.REGION_SIZE; y++) {
				nodes[x][y].reset();
			}
		}
		if (!isValidLocation(startTile, endTile)) {
			return null;
		}
		ArrayList<Node> closedNodes = new ArrayList<Node>();
		AutoSortLost openNodes = new AutoSortLost();
		Node currentNode = null;
		openNodes.add(nodes[startTile.getRegionX()][startTile.getRegionY()]);
		nodes[startTile.getRegionX()][startTile.getRegionY()].setOpen(true);
		while (openNodes.size() != 0) {
			Tile currentTile = startTile;
			if (currentNode != null) {
				currentTile = currentNode.getTile();
			}
			currentNode = openNodes.first();
			if (currentNode == nodes[endTile.getRegionX()][endTile.getRegionY()]) {
				if (isValidLocation(currentTile, endTile)) {
					break;
				}
			}
			currentNode.setOpen(false);
			openNodes.remove(currentNode);
			currentNode.setClosed(true);
			closedNodes.add(currentNode);
			for (int x = -1; x < 2; x++) {
				for (int y = -1; y < 2; y++) {
					if ((x == 0) && (y == 0)) {
						continue;
					}
					Tile newTile = region.getTile(x + currentNode.getTile().getRegionX(), y + currentNode.getTile().getRegionY());
					if (isValidLocation(currentNode.getTile(), newTile)) {
						Node neighbor = nodes[newTile.getRegionX()][newTile.getRegionY()];
						if (currentNode.getCost() + currentNode.getTile().getDistance(newTile) < neighbor.getCost()) {
							if (neighbor.isOpen()) {
								openNodes.remove(neighbor);
							}
							if (neighbor.isClosed()) {
								closedNodes.remove(neighbor);
							}
						}
						if (!neighbor.isOpen() && !neighbor.isClosed()) {
							neighbor.setCost(currentNode.getCost() + currentNode.getTile().getDistance(newTile));
							neighbor.setPreviousStep(currentNode);
							neighbor.setOpen(true);
							openNodes.add(neighbor);
						} 
					}
				}
			}
		}


		if (nodes[endTile.getRegionX()][endTile.getRegionY()].getPreviousStep() == null) {
			return null;
		}
		Path path = new Path();
		for(Node node = nodes[endTile.getRegionX()][endTile.getRegionY()]; node != nodes[startTile.getRegionX()][startTile.getRegionY()]; node = node.getPreviousStep()) {
			path.prependStep(node.getTile());
		}
		path.prependStep(startTile);
		return path;
	}

	protected boolean isValidLocation(Tile startTile, Tile endTile) {
		return ((startTile != endTile) && !endTile.getProperties().blocked());
	}

	private class AutoSortLost {

		private LinkedList<Node> list = new LinkedList<Node>();

		public void add(Node node) {
			for (int i = 0; i < list.size(); i++) {
				if (list.get(i).compareTo(node) > 0) {
					list.add(i, node);
					break;
				}
			}
			if (!list.contains(node)) {
				list.add(node);
			}
		}

		public void remove(Node node) {
			list.remove(node);
		}

		public Node first() {
			return list.get(0);
		}

		public int size() {
			return list.size();
		}

	}

	private class Node {

		private Tile tile;
		private int depth;
		private boolean open, closed;
		private double cost;
		private Node previousStep;

		public Node(Tile t) {
			this.tile = t;
		}

		public int compareTo(Node other) {	
			if (cost < other.getCost()) {
				return -1;
			} else if (cost > other.getCost()) {
				return 1;
			} else {
				return 0;
			}
		}

		public void reset() {
			closed = false;
			open = false;
			depth = 0;
			previousStep = null;
			cost = 0;
		}

		public Tile getTile() {
			return tile;
		}

		public double getCost() {
			return cost;
		}

		public void setCost(double cost) {
			this.cost = cost;
		}

		public int getDepth() {
			return depth;
		}

		public void setPreviousStep(Node previousStep) {
			depth = previousStep.getDepth() + 1;
			this.previousStep = previousStep;
		}

		public Node getPreviousStep() {
			return previousStep;
		}

		public void setOpen(boolean open) {
			this.open = open;
		}

		public boolean isOpen() {
			return open;
		}

		public void setClosed(boolean closed) {
			this.closed = closed;
		}

		public boolean isClosed() {
			return closed;
		}

	}
}
